The Internet is composed of many subnetworks having one or more hosts that are interconnected by routers. IP addressing is used to determine how a message or packet originating in a source in one subnet is to get to a destination located in a different subnetwork. Each host on the Internet has an IP address that uniquely identifies its physical location and includes information that identifies the subnet on which the host resides and also identifies the particular host. The routers then determine appropriate transmission paths for forwarding the packets across the Internet. Routers typically select transmission paths based on a predetermined cumulative metric, such as a number of hops, end-to-end delay, and cost. Where quality of service (QoS) is important, a metric related to QoS is used, wherein a small value of the metric is associated with a high level of QoS. In any case, the metric is customarily and generically referred to as cost.
Packet routing typically is performed in one of two ways: either through unicast transmission or multicast transmission. In unicast transmission, packets are sent from a single source to a single destination. Therefore, packet transmission is directed towards a single physical location that is specified by the destination host address. On the other hand, multicast transmission provides one-to-many packet transmission wherein one source is sending to multiple receivers in a given multicast group. Multicast transmission may be accomplished in several ways. In a fairly straightforward but inefficient method, the source maintains a forwarding cache that identifies all the receivers in the multicast group and sends a separate copy of the data stream to each of the receivers via unicast routing. However, if the data consists of one or more large multimedia files, the use of bandwidth becomes extremely inefficient since many of the data streams follow the same path segment through much of the network. Efficiency can be improved by controlled transmissions over a multicast topology construct, wherein at most one single copy of the data stream may traverse a link between any pair of routers.
Many techniques exist that address multicast methods of packet routing. These include: flooding, spanning tree, Steiner tree, core-based tree (CBT), reverse-path forwarding, multicast extensions to Open Shortest Path First (MOSPF) and others. Of these, only reverse-path forwarding and MOSPF (by virtue of their use of source-based shortest-path trees) support QoS routing. However, these are not very scalable. In particular, MOSPF, which is an IP multicast protocol standardized by the Internet Engineering Task Force (IETF), suffers from poor scaling because of the overhead in advertising and storing multicast state information.
Due to arbitrary tie-breaking when there are equal-cost alternate paths, MOSPF does not necessarily minimize the amount of information stored by the router in its forwarding cache. In addition, due to the inefficient structure of the forwarding cache, there is considerable redundancy in the stored information. As such, even though multicast transmission based on MOSPF is a relatively efficient method of transmitting packets to multiple destinations from a single source, it is not very scalable for IP multicast transmissions. As the number and sizes of multicast groups increase, and the amount of multimedia content being sent to distributed users increases, a need remains to improve the scalability of MOSPF for IP multicast transmissions.